package com.jiang.daily.Q1745;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/03/04 1:06
 */
class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) != s.charAt(j))
                    continue;
                dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1])
                    return true;
            }
        }

        // for (int i = 0; i < n - 2; i++) {
        //     if (dfs(dp, 0, i, 2, n)) {
        //         return true;
        //     }
        // }

        return false;

    }

    public boolean dfs(boolean[][] dp, int l, int r, int cnt, int n) {
        if (!dp[l][r])
            return false;
        --cnt;
        if (cnt == 1) {
            for (int i = r + 1; i < n - 1; i++) {
                if (dfs(dp, r + 1, i, cnt, n)) {
                    return true;
                }
            }
        } else {
            return dp[r + 1][n - 1];
        }

        return false;
    }
}
